{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Validate Binary Tree Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #union-find #graph #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #并查集 #图 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validateBinaryTreeNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二叉树上有 <code>n</code>&nbsp;个节点，按从&nbsp;<code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;编号，其中节点&nbsp;<code>i</code>&nbsp;的两个子节点分别是&nbsp;<code>leftChild[i]</code>&nbsp;和&nbsp;<code>rightChild[i]</code>。</p>\n",
    "\n",
    "<p>只有 <strong>所有</strong> 节点能够形成且 <strong>只</strong> 形成 <strong>一颗</strong>&nbsp;有效的二叉树时，返回&nbsp;<code>true</code>；否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>如果节点&nbsp;<code>i</code>&nbsp;没有左子节点，那么&nbsp;<code>leftChild[i]</code>&nbsp;就等于&nbsp;<code>-1</code>。右子节点也符合该规则。</p>\n",
    "\n",
    "<p>注意：节点没有值，本问题中仅仅使用节点编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/23/1503_ex1.png\" style=\"height: 287px; width: 195px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/23/1503_ex2.png\" style=\"height: 272px; width: 183px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/23/1503_ex3.png\" style=\"height: 174px; width: 82px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, leftChild = [1,0], rightChild = [-1,-1]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/23/1503_ex4.png\" style=\"height: 191px; width: 470px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^4</code></li>\n",
    "\t<li><code>leftChild.length == rightChild.length == n</code></li>\n",
    "\t<li><code>-1 &lt;= leftChild[i], rightChild[i] &lt;= n - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [validate-binary-tree-nodes](https://leetcode.cn/problems/validate-binary-tree-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [validate-binary-tree-nodes](https://leetcode.cn/problems/validate-binary-tree-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[1,-1,3,-1]\\n[2,-1,-1,-1]', '4\\n[1,-1,3,-1]\\n[2,3,-1,-1]', '2\\n[1,0]\\n[-1,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        # topology sort\n",
    "        indegree = Counter([x for x in leftChild + rightChild if x >= 0])\n",
    "        st = [i for i in range(n) if indegree[i] == 0]\n",
    "        if indegree and max(indegree.values()) > 1 or len(st) > 1:\n",
    "            return False\n",
    "        \n",
    "        while st:\n",
    "            p = st.pop()\n",
    "            for c in [leftChild[p], rightChild[p]]:\n",
    "                if c != -1:\n",
    "                    indegree[c] -= 1\n",
    "                    if not indegree[c]:\n",
    "                        st.append(c)\n",
    "        return not any(indegree.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        return (leftChild + rightChild).count(-1) == n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        childAndParent = [-1] * n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for childArr in [leftChild, rightChild]:\n",
    "                if childArr[i] != -1:\n",
    "                    if childAndParent[childArr[i]] != -1:\n",
    "                        return False\n",
    "                    childAndParent[childArr[i]] = i  # 父亲是i\n",
    "                    cnt += 1\n",
    "\n",
    "        # 孩子节点的个数必然是n - 1 不然就不是连通的，或者没有根节点，也就是存在环\n",
    "        if cnt != n - 1:\n",
    "            return False\n",
    "\n",
    "        for i in range(n):\n",
    "            if childAndParent[i] == -1:\n",
    "                continue\n",
    "            visited = set()\n",
    "            child, parent = i, childAndParent[i]\n",
    "            childAndParent[child] = -1  # 置为已读\n",
    "            visited.add(child)\n",
    "            while childAndParent[parent] != -1:\n",
    "                visited.add(parent)\n",
    "                childAndParent[parent], parent = -1, childAndParent[parent]\n",
    "                if parent in visited:  # 存在环\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        if n - leftChild.count(-1) - rightChild.count(-1) != -1:\n",
    "            return False\n",
    "\n",
    "        parents = [-1] * n\n",
    "        for i, c in enumerate(leftChild):\n",
    "            if c != -1:\n",
    "                if parents[c] != -1:\n",
    "                    return False\n",
    "                parents[c] = i\n",
    "        for i, c in enumerate(rightChild):\n",
    "            if c != -1:\n",
    "                if parents[c] != -1:\n",
    "                    return False\n",
    "                parents[c] = i\n",
    "        \n",
    "        if parents.count(-1) != 1:\n",
    "            return False\n",
    "        \n",
    "        d = [parents.index(-1)]\n",
    "        idx = 0\n",
    "        while idx < len(d):\n",
    "            if leftChild[d[idx]] != -1:\n",
    "                d.append(leftChild[d[idx]])\n",
    "            if rightChild[d[idx]] != -1:\n",
    "                d.append(rightChild[d[idx]])\n",
    "            idx += 1\n",
    "        return len(d) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        indeg = [0] * n\n",
    "        for u in leftChild:\n",
    "            if u != -1:\n",
    "                indeg[u] += 1\n",
    "        for u in rightChild:\n",
    "            if u != -1:\n",
    "                indeg[u] += 1\n",
    "        \n",
    "        root = -1\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return False\n",
    "\n",
    "        \n",
    "        seen = set([root])\n",
    "        q = collections.deque([root])\n",
    "\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            if leftChild[u] != -1:\n",
    "                if leftChild[u] in seen:\n",
    "                    return False\n",
    "                seen.add(leftChild[u])\n",
    "                q.append(leftChild[u])\n",
    "            if rightChild[u] != -1:\n",
    "                if rightChild[u] in seen:\n",
    "                    return False\n",
    "                seen.add(rightChild[u])\n",
    "                q.append(rightChild[u])\n",
    "        \n",
    "        return len(seen) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        \n",
    "        if n <= 1:\n",
    "            return True        \n",
    "        # 找root，n中没有出现过的就是root，加入到root中，如果root数量不是1，那么肯定false\n",
    "        root = []\n",
    "        used = []\n",
    "        \n",
    "        hash_l = {}\n",
    "        hash_r = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            if leftChild[i] not in hash_l:\n",
    "                hash_l[leftChild[i]] = 1\n",
    "            else:\n",
    "                hash_l[leftChild[i]] += 1\n",
    "\n",
    "            if rightChild[i] not in hash_r:\n",
    "                hash_r[rightChild[i]] = 1\n",
    "            else:\n",
    "                hash_r[rightChild[i]] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in hash_l and i not in hash_r:\n",
    "                root.append(i)\n",
    "            if len(root) == 2:\n",
    "                return False\n",
    "        \n",
    "        if len(root) == 0:\n",
    "            return False\n",
    "        \n",
    "        value = root[0]        \n",
    "        #node = TreeNode(value)\n",
    "        used.append(value)\n",
    "        stack = [value]\n",
    "        \n",
    "        while stack:\n",
    "            val = stack.pop(0)       \n",
    "            if leftChild[val] != -1:\n",
    "                if leftChild[val] in used:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur_left = leftChild[val]\n",
    "                    used.append(cur_left)\n",
    "                    stack.append(cur_left)\n",
    "\n",
    "            if rightChild[val] != -1:\n",
    "                if rightChild[val] in used:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur_right = rightChild[val]\n",
    "                    used.append(cur_right)\n",
    "                    stack.append(cur_right)\n",
    "        \n",
    "        \n",
    "        if len(used) != n:\n",
    "            return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #4\n",
    "    #[1,0,3,-1]\n",
    "    #[-1,-1,-1,-1]\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        parent = [-1]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            if leftChild[i] != -1:\n",
    "                if parent[leftChild[i]] == -1:\n",
    "                    parent[leftChild[i]] = i\n",
    "                elif parent[leftChild[i]] != i:\n",
    "                    return False\n",
    "            if rightChild[i] != -1:\n",
    "                if parent[rightChild[i]] == -1:\n",
    "                    parent[rightChild[i]] = i\n",
    "                elif parent[rightChild[i]] != i:\n",
    "                    return False\n",
    "        print(parent)\n",
    "        # check if ring is in tree\n",
    "        rootSum = 0\n",
    "        #visited = [0]*n\n",
    "        for i in range(n):\n",
    "            if parent[i] == -1:\n",
    "                rootSum += 1\n",
    "                continue\n",
    "            visited = [0]*n\n",
    "            visited[i] = 1\n",
    "            parentj = parent[i]\n",
    "            while parentj != -1:\n",
    "                if visited[parentj] == 1:\n",
    "                    return False\n",
    "                visited[parentj] = 1\n",
    "                parentj = parent[parentj]\n",
    "\n",
    "        return True if rootSum == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        # 两个条件：\n",
    "        # 1.低位指向高位\n",
    "        # 2.除根节点外，入度为1\n",
    "        nums = [0] * n\n",
    "        for i in range(n):\n",
    "            if leftChild[i] != -1:\n",
    "                if leftChild[i] <= i and nums[i] != 0:\n",
    "                    return False\n",
    "                nums[leftChild[i]] += 1\n",
    "            if rightChild[i] != -1:\n",
    "                if rightChild[i] <= i and nums[i] != 0:\n",
    "                    return False\n",
    "                nums[rightChild[i]] += 1\n",
    "        \n",
    "        num_root = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > 1:\n",
    "                return False\n",
    "            if nums[i] == 0:\n",
    "                num_root += 1\n",
    "        return num_root == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        parents=[i for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            l,r=leftChild[i],rightChild[i]\n",
    "            p=self.get_parent(parents,i)\n",
    "            if l!=-1:\n",
    "                if parents[l]!=l or p==l:\n",
    "                    return False\n",
    "                else:\n",
    "                    parents[l]=p\n",
    "            if r!=-1:\n",
    "                if parents[r]!=r or p==r:\n",
    "                    return False\n",
    "                else:\n",
    "                    parents[r]=p\n",
    "        \n",
    "        p=self.get_parent(parents,0)\n",
    "        for i in range(1,n):\n",
    "            if self.get_parent(parents,i)!=p:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "    \n",
    "    def get_parent(self,parents,index):\n",
    "        p=index\n",
    "        while parents[p]!=p:\n",
    "            p=parents[p]\n",
    "        \n",
    "        while parents[index]!=p:\n",
    "            t=parents[index]\n",
    "            parents[index]=p\n",
    "            index=t\n",
    "        \n",
    "        return p\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        bk = set()\n",
    "        cnt1 = cnt2 = 0\n",
    "        for i, j in enumerate(leftChild):\n",
    "            if j != -1:\n",
    "                if i in bk and j < i:\n",
    "                    return False\n",
    "                bk.add(j)\n",
    "                cnt1 += 1\n",
    "        for i, j in enumerate(rightChild):\n",
    "            if j != -1:\n",
    "                if i in bk and j < i or j in bk:\n",
    "                    return False\n",
    "                bk.add(j)\n",
    "                cnt2 += 1\n",
    "        return cnt1 + cnt2 + 1 == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        empty = 0\n",
    "        indeg = [0] * n\n",
    "        for x in chain(leftChild, rightChild):\n",
    "            if x == -1:\n",
    "                empty += 1\n",
    "            else:\n",
    "                indeg[x] += 1\n",
    "                if indeg[x] >= 2:\n",
    "                    return False\n",
    "        if empty != n+1:\n",
    "            return False\n",
    "        \n",
    "        root = indeg.index(0)\n",
    "\n",
    "        notvis = n\n",
    "        q = [root]\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            notvis -= 1\n",
    "            if (y := leftChild[x]) != -1:\n",
    "                q.append(y)\n",
    "            if (y := rightChild[x]) != -1:\n",
    "                q.append(y)\n",
    "\n",
    "        return notvis == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        ischild=[0]*n\n",
    "        for i in range (0,n):\n",
    "            if leftChild[i]!=-1:\n",
    "                ischild[leftChild[i]]=1\n",
    "            if rightChild[i]!=-1:\n",
    "                ischild[rightChild[i]]=1\n",
    "        if Counter(ischild)[0]!=1:\n",
    "            return False\n",
    "        r=ischild.index(0)\n",
    "        queue=[r]\n",
    "        visited=[0]*n\n",
    "        visited[r]=1\n",
    "        while queue:\n",
    "            x=queue.pop(0)\n",
    "            if leftChild[x]!=-1:\n",
    "                if visited[leftChild[x]]==0:\n",
    "                    visited[leftChild[x]]=1\n",
    "                    queue.append(leftChild[x])\n",
    "                else:\n",
    "                    return False\n",
    "            if rightChild[x]!=-1:\n",
    "                if visited[rightChild[x]]==0:\n",
    "                    visited[rightChild[x]]=1\n",
    "                    queue.append(rightChild[x])\n",
    "                else:\n",
    "                    return False\n",
    "        return (sum(visited)==n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        child_set = set()\n",
    "        for child in leftChild:\n",
    "            child_set.add(child)\n",
    "        for child in rightChild:\n",
    "            child_set.add(child)\n",
    "        \n",
    "        root = None\n",
    "        for index in range(n):\n",
    "            if index not in child_set:\n",
    "                if root is None:\n",
    "                    root = index\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        if root is None:\n",
    "            return False\n",
    "\n",
    "        q = [root]\n",
    "        l = 0\n",
    "        r = 1\n",
    "        used = [False] * n\n",
    "        used[root] = True\n",
    "        while l < r:\n",
    "            now = q[l]\n",
    "            l += 1\n",
    "            if leftChild[now] != -1:\n",
    "                if used[leftChild[now]]:\n",
    "                    return False\n",
    "                used[leftChild[now]] = True\n",
    "                q.append(leftChild[now])\n",
    "                r += 1\n",
    "            if rightChild[now] != -1:\n",
    "                if used[rightChild[now]]:\n",
    "                    return False\n",
    "                used[rightChild[now]] = True\n",
    "                q.append(rightChild[now])\n",
    "                r += 1\n",
    "\n",
    "        return len(q) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        indeg = [0] * n \n",
    "        for u in leftChild:\n",
    "            if u != -1:\n",
    "                indeg[u] += 1\n",
    "        for u in rightChild:\n",
    "            if u != -1:\n",
    "                indeg[u] += 1\n",
    "        root = -1\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return False\n",
    "        \n",
    "        seen = set([root])\n",
    "        q = collections.deque([root])\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            if leftChild[u] != -1:\n",
    "                if leftChild[u] in seen:\n",
    "                    return False\n",
    "                q.append(leftChild[u])\n",
    "                seen.add(leftChild[u])\n",
    "            if rightChild[u] != -1:\n",
    "                if rightChild[u] in seen:\n",
    "                    return False\n",
    "                q.append(rightChild[u])\n",
    "                seen.add(rightChild[u])\n",
    "        return len(seen) == n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:   \n",
    "        if len(se := set(range(n)) - set(leftChild + rightChild)) != 1: return False\n",
    "        se_, se1 = set(), set(se)\n",
    "        while se:\n",
    "            for i in se:\n",
    "                if leftChild[i] in se1 or rightChild[i] in se1: \n",
    "                    return False\n",
    "                else:\n",
    "                    se_ |= {leftChild[i], rightChild[i]} - {-1}\n",
    "                    se1 |= {leftChild[i], rightChild[i]} - {-1}\n",
    "            se, se_ = se_, set()\n",
    "        return len(se1) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        childs = set([])\n",
    "        childs.update(leftChild)\n",
    "        childs.update(rightChild)\n",
    "        root = list(set([i for i in range(n)]+[-1]) - childs)\n",
    "        if len(root) != 1:\n",
    "            return False\n",
    "        to_visit = [root[0]]\n",
    "        fathers = {}\n",
    "        while to_visit:\n",
    "            tmp = []\n",
    "            for node in to_visit:\n",
    "                fathers[str(node)] = node\n",
    "                if leftChild[node] != -1:\n",
    "                    if str(leftChild[node]) in fathers or leftChild[node] in tmp:\n",
    "                        return False\n",
    "                    tmp.append(leftChild[node])\n",
    "                if rightChild[node] != -1:\n",
    "                    if str(rightChild[node]) in fathers or rightChild[node] in tmp:\n",
    "                        return False\n",
    "                    tmp.append(rightChild[node])\n",
    "            to_visit = tmp\n",
    "        if len(fathers.keys()) == n:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        retVal = False\n",
    "\n",
    "        root = -1\n",
    "        children = set(leftChild) | set(rightChild)\n",
    "        for i in range(n):\n",
    "            if i not in children:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return retVal\n",
    "\n",
    "        visited = {root}\n",
    "        bfsQueue = deque([root])\n",
    "        while bfsQueue:\n",
    "            node = bfsQueue.popleft()\n",
    "            for child in [leftChild[node], rightChild[node]]:\n",
    "                if child == -1:\n",
    "                    continue\n",
    "                if child in visited:\n",
    "                    return retVal\n",
    "                bfsQueue.append(child)\n",
    "                visited.add(child)\n",
    "        if len(visited) == n:\n",
    "            retVal = True\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        root = list(set(range(n)) - (set(leftChild) | set(rightChild)))\n",
    "        if len(root) != 1:\n",
    "            return False\n",
    "        visit = [False] * n\n",
    "        visit[root[0]] = True\n",
    "        queue = [root[0]]\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            for x in queue:\n",
    "                if leftChild[x] != -1:\n",
    "                    if visit[leftChild[x]]: return False\n",
    "                    new_queue.append(leftChild[x])\n",
    "                    visit[leftChild[x]] = True\n",
    "                if rightChild[x] != -1:\n",
    "                    if visit[rightChild[x]]: return False\n",
    "                    new_queue.append(rightChild[x])\n",
    "                    visit[rightChild[x]] = True\n",
    "            queue = new_queue\n",
    "        return True and all(visit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        parent = [i for i in range(n)]\n",
    "        cnt = 0\n",
    "\n",
    "        def find(x):\n",
    "            if x == parent[x]: return x\n",
    "            parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        in_d = [0] * n\n",
    "        for i, (vl, vr) in enumerate(zip(leftChild, rightChild)):\n",
    "            r0 = find(i)\n",
    "            if vl != -1:\n",
    "                in_d[vl] += 1\n",
    "                r1 = find(vl)\n",
    "                if r0 != r1:\n",
    "                    cnt += 1\n",
    "                    parent[r1] = r0\n",
    "                else:\n",
    "                    return False\n",
    "            if vr != -1:\n",
    "                in_d[vr] += 1\n",
    "                r2 = find(vr)\n",
    "                if r0 != r2:\n",
    "                    cnt += 1\n",
    "                    parent[r2] = r0\n",
    "                else:\n",
    "                    return False\n",
    "        return cnt == n - 1 and sum([1 for v in in_d if v == 0]) == 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        indeg = [0]*n\n",
    "        outdeg = [0]*n\n",
    "        edges = 0\n",
    "        parent = list(range(n))\n",
    "\n",
    "        def find(idx):\n",
    "            if parent[idx] != idx:\n",
    "                parent[idx] = find(parent[idx])\n",
    "            return parent[idx]\n",
    "        \n",
    "        def union(idx1, idx2):\n",
    "            parent[find(idx1)] = find(idx2)\n",
    "\n",
    "        def connected(idx1, idx2):\n",
    "            return find(idx1) == find(idx2)\n",
    "\n",
    "        for i in range(n):\n",
    "            if leftChild[i] != -1:\n",
    "                outdeg[i] += 1\n",
    "                indeg[leftChild[i]] += 1\n",
    "                edges += 1\n",
    "                if connected(i, leftChild[i]):\n",
    "                    return False\n",
    "                else:\n",
    "                    union(i, leftChild[i])\n",
    "            if rightChild[i] != -1:\n",
    "                outdeg[i] += 1\n",
    "                indeg[rightChild[i]] += 1\n",
    "                edges += 1\n",
    "                if connected(i, rightChild[i]):\n",
    "                    return False\n",
    "                else:\n",
    "                    union(i, rightChild[i])\n",
    "        if edges != n-1:\n",
    "            return False\n",
    "        for i in indeg:\n",
    "            if i>=2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        #不是真的二叉树,只是列表\n",
    "        #验证是二叉树的条件:1, 没有交叉 2,每个点都在树上\n",
    "        ##追寻已经上树的点,进行无重复延伸\n",
    "        #先找root\n",
    "        ll = set(leftChild)\n",
    "        rr = set(rightChild)\n",
    "        lr = ll|rr\n",
    "        tot = set([x for x in range(n)]+[-1])\n",
    "        res = lr ^ tot\n",
    "        # print(res)\n",
    "        if len(res) != 1:return False\n",
    "        root = res.pop()\n",
    "        \n",
    "        stack = {root}\n",
    "        nxt = stack\n",
    "        while nxt:\n",
    "            t = nxt.copy()\n",
    "            nxt = set()\n",
    "            for x in t:\n",
    "                left = leftChild[x]\n",
    "                right = rightChild[x]\n",
    "                if left in stack:\n",
    "                    return False\n",
    "                if left != -1:\n",
    "                    stack.add(left)\n",
    "                    nxt.add(left)\n",
    "                if right in stack:\n",
    "                    return False\n",
    "                if right != -1:\n",
    "                    stack.add(right)\n",
    "                    nxt.add(right)\n",
    "        # print(stack)\n",
    "        return  len(stack) == n\n",
    "        ##反例  0 不是也行...\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\r\n",
    "        def findAncestor(x):\r\n",
    "            uf.setdefault(x, x)\r\n",
    "            if x != uf[x]:\r\n",
    "                uf[x] = findAncestor(uf[x])\r\n",
    "            return uf[x]\r\n",
    "        \r\n",
    "        def union(x, y):\r\n",
    "            nonlocal count \r\n",
    "            parent_x = findAncestor(x)\r\n",
    "            parent_y = findAncestor(y)\r\n",
    "            if parent_x == parent_y:\r\n",
    "                return\r\n",
    "            count -= 1\r\n",
    "            uf[parent_x] = parent_y\r\n",
    "        \r\n",
    "        uf = {}\r\n",
    "        count = n\r\n",
    "        indegree = [0] * n # remember to check the indegree because the arrow is directional\r\n",
    "        for i in range(n):\r\n",
    "            if leftChild[i] != -1: \r\n",
    "                if findAncestor(leftChild[i]) == findAncestor(i):\r\n",
    "                    return False\r\n",
    "                union(leftChild[i], i)\r\n",
    "                indegree[leftChild[i]] += 1\r\n",
    "            if rightChild[i] != -1: \r\n",
    "                if findAncestor(rightChild[i]) == findAncestor(i):\r\n",
    "                    return False\r\n",
    "                union(rightChild[i], i)\r\n",
    "                indegree[rightChild[i]] += 1\r\n",
    "        if max(indegree) > 1:\r\n",
    "            return False\r\n",
    "        return True if count == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "\n",
    "        def dfs(leftChild,rightChild,x):\n",
    "            if x in seen:\n",
    "                return False\n",
    "            seen.add(x)\n",
    "            flag=True\n",
    "            if leftChild[x]!=-1:\n",
    "                flag=dfs(leftChild,rightChild,leftChild[x]) and flag\n",
    "            if rightChild[x]!=-1:\n",
    "                flag=dfs(leftChild,rightChild,rightChild[x]) and flag\n",
    "            return flag\n",
    "\n",
    "        def bfs(leftChild,rightChild,root):\n",
    "            seen.add(root)\n",
    "            q = collections.deque([root])\n",
    "            while len(q) > 0:\n",
    "                u = q.popleft()\n",
    "                if leftChild[u] != -1:\n",
    "                    if leftChild[u] in seen:\n",
    "                        return False\n",
    "                    seen.add(leftChild[u])\n",
    "                    q.append(leftChild[u])\n",
    "                if rightChild[u] != -1:\n",
    "                    if rightChild[u] in seen:\n",
    "                        return False\n",
    "                    seen.add(rightChild[u])\n",
    "                    q.append(rightChild[u])\n",
    "\n",
    "\n",
    "        indegree=[0]*n \n",
    "        for i in range(n):\n",
    "            if leftChild[i]!=-1:\n",
    "                indegree[leftChild[i]]+=1\n",
    "            if rightChild[i]!=-1:\n",
    "                indegree[rightChild[i]]+=1\n",
    "        root=-1\n",
    "        for i in range(n):\n",
    "            if indegree[i]==0:\n",
    "                root=i\n",
    "                break\n",
    "        if root==-1:\n",
    "            return False\n",
    "\n",
    "        # seen = set([])\n",
    "\n",
    "        # # is_cycle=bfs(leftChild,rightChild,root)\n",
    "\n",
    "        # # return len(seen)==n and is_cycle\n",
    "\n",
    "        # bfs(leftChild,rightChild,root)\n",
    "        \n",
    "\n",
    "        # return len(seen)==n\n",
    "\n",
    "       \n",
    "        seen = set([root])\n",
    "        q = collections.deque([root])\n",
    "\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            if leftChild[u] != -1:\n",
    "                if leftChild[u] in seen:\n",
    "                    return False\n",
    "                seen.add(leftChild[u])\n",
    "                q.append(leftChild[u])\n",
    "            if rightChild[u] != -1:\n",
    "                if rightChild[u] in seen:\n",
    "                    return False\n",
    "                seen.add(rightChild[u])\n",
    "                q.append(rightChild[u])\n",
    "        \n",
    "        return len(seen) == n\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "#         indeg = [0] * n\n",
    "#         for u in leftChild:\n",
    "#             if u != -1:\n",
    "#                 indeg[u] += 1\n",
    "#         for u in rightChild:\n",
    "#             if u != -1:\n",
    "#                 indeg[u] += 1\n",
    "        \n",
    "#         root = -1\n",
    "#         for i in range(n):\n",
    "#             if indeg[i] == 0:\n",
    "#                 root = i\n",
    "#                 break\n",
    "#         if root == -1:\n",
    "#             return False\n",
    "\n",
    "        \n",
    "#         seen = set([root])\n",
    "#         q = collections.deque([root])\n",
    "\n",
    "#         while len(q) > 0:\n",
    "#             u = q.popleft()\n",
    "#             if leftChild[u] != -1:\n",
    "#                 if leftChild[u] in seen:\n",
    "#                     return False\n",
    "#                 seen.add(leftChild[u])\n",
    "#                 q.append(leftChild[u])\n",
    "#             if rightChild[u] != -1:\n",
    "#                 if rightChild[u] in seen:\n",
    "#                     return False\n",
    "#                 seen.add(rightChild[u])\n",
    "#                 q.append(rightChild[u])\n",
    "        \n",
    "#         return len(seen) == n\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "grey = -1\n",
    "root = -2\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        color = [0] * n \n",
    "        current_color = 0\n",
    "        def dfs(cur):\n",
    "            if cur == -1:\n",
    "                return True\n",
    "            if color[cur] != 0:\n",
    "                if color[cur] == grey or color[cur] == current_color: # forward edge and back edge\n",
    "                    return False\n",
    "                else:\n",
    "                    color[cur] = current_color\n",
    "                    return True\n",
    "            color[cur] = grey\n",
    "            flag = dfs(leftChild[cur]) and dfs(rightChild[cur])\n",
    "            color[cur] = current_color\n",
    "            return flag\n",
    "        for i in range(n):\n",
    "            if color[i] == 0:\n",
    "                current_color += 1\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "                color[i] = root\n",
    "        return color.count(root) == 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            if leftChild[i] == i or rightChild[i] == i:  # 自环\n",
    "                return False\n",
    "            root = uf.find(i)\n",
    "            if leftChild[i] == root or rightChild[i] == root:  # 环路\n",
    "                return False\n",
    "            if leftChild[i] >= 0:\n",
    "                if uf.find(leftChild[i]) != leftChild[i]:  # 子节点有多个父节点\n",
    "                    return False\n",
    "                uf.union(i, leftChild[i])\n",
    "            if rightChild[i] >= 0:\n",
    "                if uf.find(rightChild[i]) != rightChild[i]:  # 子节点有多个父节点\n",
    "                    return False\n",
    "                uf.union(i, rightChild[i])\n",
    "        root = uf.find(0)\n",
    "        for i in range(1, n):  # 验证是否有多个根节点\n",
    "            if root != uf.find(i):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "# 定义并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, i, j):\n",
    "        rooti = self.find(i)\n",
    "        rootj = self.find(j)\n",
    "        if rooti != rootj:\n",
    "            self.parent[rootj] = rooti"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        countLst = [0 for _ in range(n)]\n",
    "\n",
    "        # 计算有所结点的入度，以便找出根结点\n",
    "        # 因为，根结点的入度为 0\n",
    "        roots = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if leftChild[i] != -1:\n",
    "                roots[leftChild[i]] += 1\n",
    "            if rightChild[i] != -1:\n",
    "                roots[rightChild[i]] += 1\n",
    "        \n",
    "        # 如果没有根结点，或者有多个入度为 0 的结点\n",
    "        # 如果是第一种情况，说明这棵树中有环\n",
    "        # 如果是第二种情况，则说明有多棵树\n",
    "        countRoot = roots.count(0)\n",
    "        if countRoot == 0 or countRoot > 1:\n",
    "            return False       \n",
    "        root = roots.index(0)       \n",
    "    \n",
    "        # 从根结点出发，去判断是否每个节点都被访问了一次，且只能被访问一次\n",
    "        if getSubSet(root, leftChild, rightChild, countLst) == -1:\n",
    "            return False\n",
    "        \n",
    "        # 如果 countLst.count(0) != 0，则说明树中有些结点没有被访问到\n",
    "        # 也就是说，如果树中有环存在，就会出现这种情况\n",
    "        # 比如：0->1, 1->0, 2->3, 3->-1, 3 后面没有结点，那么 2 就是根结点\n",
    "        return countLst.count(0) == 0\n",
    "\n",
    "def getSubSet(node, leftChild, rightChild, countLst):  \n",
    "    # 当前结点访问次数加一\n",
    "    countLst[node] += 1\n",
    "    \n",
    "    # 如果当前结点加一后，大于 1，则说明已经被重复访问了\n",
    "    if countLst[node] > 1:\n",
    "        return -1  \n",
    "    else:\n",
    "        # 访问左结点\n",
    "        if leftChild[node] != -1:\n",
    "            if getSubSet(leftChild[node], leftChild, rightChild, countLst) == -1:\n",
    "                return -1   \n",
    "\n",
    "        # 访问右结点     \n",
    "        if rightChild[node] != -1:\n",
    "            if getSubSet(rightChild[node], leftChild, rightChild, countLst) == -1:\n",
    "                return -1\n",
    "\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        \n",
    "        self.count = 0\n",
    "        self.parent = [-1 for _ in range(n)]\n",
    "        self.rank = [0 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            self.parent[i] = i\n",
    "            self.count += 1\n",
    "    \n",
    "    # 路径压缩\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        \n",
    "        return self.parent[x]\n",
    "\n",
    "    # 按秩合并\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "            \n",
    "            self.count -= 1\n",
    "\n",
    "    # 获取连通分量个数\n",
    "    def get_count(self) -> int:\n",
    "        return self.count\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(\n",
    "        self, \n",
    "        n: int, \n",
    "        leftChild: List[int], \n",
    "        rightChild: List[int]\n",
    "    ) -> bool:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        outdegree = defaultdict(int)\n",
    "        edges = set()\n",
    "\n",
    "        for node, (left, right) in enumerate(zip(leftChild, rightChild)):\n",
    "            if left != -1 or right != -1:\n",
    "                if left != -1:\n",
    "                    graph[node].append(left)\n",
    "                    # 排除自环情况\n",
    "                    if node == left:\n",
    "                        return False\n",
    "                    \n",
    "                    indegree[left] += 1\n",
    "                    outdegree[node] += 1\n",
    "\n",
    "                    edges.add((node, left))\n",
    "\n",
    "                if right != -1:\n",
    "                    graph[node].append(right)\n",
    "                    # 排除自环的情况\n",
    "                    if node == right:\n",
    "                        return False\n",
    "                    \n",
    "                    indegree[right] += 1\n",
    "                    outdegree[node] += 1\n",
    "\n",
    "                    edges.add((node, right))\n",
    "\n",
    "        if len(edges) != n - 1:\n",
    "            return False\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for node in range(n):\n",
    "            indeg = indegree[node]\n",
    "            outdeg = outdegree[node]\n",
    "\n",
    "            if indeg > 1 or outdeg > 2:\n",
    "                return False\n",
    "\n",
    "            if indeg == 0:\n",
    "                cnt += 1\n",
    "\n",
    "        if cnt > 1 or cnt == 0:\n",
    "            return False\n",
    "\n",
    "        ufs = UnionFindSet(n)\n",
    "        for u, adju in graph.items():\n",
    "            for v in adju:\n",
    "                ufs.union(u, v)\n",
    "\n",
    "        return ufs.get_count() == 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        visited = [0] * n\n",
    "        for i in range(n):\n",
    "            if i not in leftChild and i not in rightChild:\n",
    "                break\n",
    "        if i == n:\n",
    "            return False\n",
    "        if self.RF(leftChild, rightChild, i, visited):\n",
    "            for i in visited:\n",
    "                if i == 0:\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    \n",
    "    def RF(self, leftChild: List[int], rightChild: List[int], loc: int, visited: List[int]) -> bool:\n",
    "        if loc == -1:\n",
    "            return True\n",
    "        if visited[loc] == 1:\n",
    "            return False\n",
    "        else:\n",
    "            visited[loc] = 1\n",
    "            return self.RF(leftChild, rightChild, leftChild[loc], visited) and \\\n",
    "                self.RF(leftChild, rightChild, rightChild[loc], visited)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def BiTreeTraverse(root, leftChild, rightChild):\n",
    "    if root == -1:\n",
    "        return 0\n",
    "    elif leftChild[root] == -1 and rightChild[root] == -1:\n",
    "        return 1\n",
    "\n",
    "    return 1 + BiTreeTraverse(leftChild[root], leftChild, rightChild) \\\n",
    "            + BiTreeTraverse(rightChild[root], leftChild, rightChild)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "\n",
    "        if n == 1:\n",
    "            if leftChild[0] == -1 and rightChild[0] == -1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        visited = [False] * n\n",
    "        parent = [-1] * n\n",
    "        # visited[0] = True\n",
    "        count = 0\n",
    "        i = 0\n",
    "        for left, right in zip(leftChild, rightChild):\n",
    "            if left != -1 or right != -1:\n",
    "                # print(\"*******\", i, visited[i], left, right)\n",
    "                # if not visited[i]:\n",
    "                #     return False\n",
    "\n",
    "                if left != -1:\n",
    "                    if not visited[left]:\n",
    "                        visited[left] = True\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        return False\n",
    "\n",
    "                    if left == parent[i]:\n",
    "                        return False\n",
    "\n",
    "                    parent[left] = i\n",
    "\n",
    "                if right != -1:\n",
    "                    if not visited[right]:\n",
    "                        visited[right] = True\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        return False\n",
    "\n",
    "                    if right == parent[i]:\n",
    "                        return False\n",
    "\n",
    "                    parent[right] = i\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        # print(count, visited, parent)\n",
    "\n",
    "        if count == n-1:  # and sum(visited) == n-1:\n",
    "            cnt = 0\n",
    "            pos = -1\n",
    "            for i, x in enumerate(parent):\n",
    "                if x == -1:\n",
    "                    cnt += 1\n",
    "                    pos = i\n",
    "                    if cnt == 2:\n",
    "                        return False\n",
    "\n",
    "            if pos in parent and n == BiTreeTraverse(pos, leftChild, rightChild):\n",
    "            # if pos >= 0 and n == BiTreeTraverse(pos, leftChild, rightChild):\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        in_deg = [0] * n\n",
    "        for val in leftChild:\n",
    "            if val != -1:\n",
    "                in_deg[val] += 1\n",
    "        for val in rightChild:\n",
    "            if val != -1:\n",
    "                in_deg[val] += 1\n",
    "\n",
    "        root = -1\n",
    "        for i, v in enumerate(in_deg):\n",
    "            if v == 0:\n",
    "                if root != -1:\n",
    "                    return False\n",
    "                root = i\n",
    "            elif v > 1:\n",
    "                return False\n",
    "\n",
    "        if root == -1:\n",
    "            return False\n",
    "\n",
    "        visited = [0] * n\n",
    "\n",
    "        def dfs(cur: int):\n",
    "            visited[cur] = 1\n",
    "            if leftChild[cur] != -1:\n",
    "                dfs(leftChild[cur])\n",
    "            if rightChild[cur] != -1:\n",
    "                dfs(rightChild[cur])\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return sum(visited) == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        parent = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if(x != parent[x]):\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            parent[find(x)] = find(y)\n",
    "        node_before = [-1] * n\n",
    "        for l,r in zip(leftChild,rightChild):\n",
    "            if(l != -1):\n",
    "                node_before[l] += 1\n",
    "            if(r != -1):\n",
    "                node_before[r] += 1\n",
    "        root = -1\n",
    "        for i in range(n):\n",
    "            if(node_before[i] == -1):\n",
    "                if(root == -1):\n",
    "                    root = i\n",
    "                else:\n",
    "                    return False\n",
    "        if(root == -1):\n",
    "            return False\n",
    "        node = 0\n",
    "        for l,r in zip(leftChild,rightChild):\n",
    "            if(l != -1 and parent[l] != l):\n",
    "                return False\n",
    "            if(l != -1):\n",
    "                union(l,node)\n",
    "            if(r != -1 and parent[r] != r):\n",
    "                return False\n",
    "            if(r != -1):\n",
    "                union(r,node)\n",
    "            node += 1\n",
    "        for i in range(n):\n",
    "            if(i == root):\n",
    "                continue\n",
    "            if(find(i) != root):\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "\n",
    "        # 记录每个节点的⼊度\n",
    "        indegree = [0] * n\n",
    "        for left in leftChild:\n",
    "            if left != -1:\n",
    "                indegree[left] += 1\n",
    "\n",
    "        for right in rightChild:\n",
    "            if right != -1:\n",
    "                indegree[right] += 1\n",
    "\n",
    "        #  按道理应该有且只有根节点的⼊度为 0，\n",
    "        #  其他节点的⼊度都必须为 1\n",
    "        root = -1\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                if root != -1:\n",
    "                    # 有多个⼊度为 0 的节点\n",
    "                    return False\n",
    "                root = i\n",
    "            elif indegree[i] != 1:\n",
    "                #  除了根节点外其他节点的⼊度都必须为 1\n",
    "                return False\n",
    "\n",
    "        # 没有根节点\n",
    "        if root == -1:\n",
    "            return False\n",
    "\n",
    "        # DFS\n",
    "        self.leftChild = leftChild\n",
    "        self.rightChild = rightChild\n",
    "        self.visited = [False] * n\n",
    "        self.hasCycle = False\n",
    "\n",
    "        def traverse(root):\n",
    "            if root == -1 or self.hasCycle:\n",
    "                return\n",
    "\n",
    "            if self.visited[root]:\n",
    "                self.hasCycle = True\n",
    "                return\n",
    "\n",
    "            self.visited[root] = True\n",
    "\n",
    "            traverse(self.leftChild[root])\n",
    "            traverse(self.rightChild[root])\n",
    "\n",
    "        traverse(root)\n",
    "        if self.hasCycle:\n",
    "            return False\n",
    "\n",
    "        for i in range(n):\n",
    "            # 如果一次遍历没有经过所有节点，也不是合法二叉树\n",
    "            if not self.visited[i]:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        inc = [0 for _ in range(n)]\n",
    "        x, rt = 0, -1\n",
    "        for i in range(n):\n",
    "            if leftChild[i]!=-1:\n",
    "                inc[leftChild[i]] += 1\n",
    "            if rightChild[i]!=-1:\n",
    "                inc[rightChild[i]] += 1\n",
    "        for i in range(n):\n",
    "            if inc[i]==0:\n",
    "                x += 1\n",
    "                if x>1:\n",
    "                    return False\n",
    "                rt = i\n",
    "        c = [0 for _ in range(n)]\n",
    "        self.x = 0\n",
    "        def dfs(i):\n",
    "            if i==-1:\n",
    "                return True\n",
    "            if c[i]!=0:\n",
    "                return False\n",
    "            c[i] = 1\n",
    "            self.x += 1\n",
    "            if not dfs(leftChild[i]):\n",
    "                return False\n",
    "            if not dfs(rightChild[i]):\n",
    "                return False\n",
    "            c[i] = 2\n",
    "            return True\n",
    "        if not dfs(rt):\n",
    "            return False\n",
    "        return self.x==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(\n",
    "        self, n: int, leftChild: List[int], rightChild: List[int]\n",
    "    ) -> bool:\n",
    "        # left <= mid <= right\n",
    "\n",
    "        # find root\n",
    "        q = list(zip(leftChild, rightChild))\n",
    "        deg = [0] * n\n",
    "        for left, right in q:\n",
    "            if left != -1:\n",
    "                deg[left] += 1\n",
    "            if right != -1:\n",
    "                deg[right] += 1\n",
    "\n",
    "        root = [i for i, d in enumerate(deg) if d == 0]\n",
    "\n",
    "        if len(root) != 1:\n",
    "            return False\n",
    "\n",
    "        root = root[0]\n",
    "        vis = [0] * n\n",
    "\n",
    "        def dfs(root):\n",
    "            vis[root] += 1\n",
    "            if vis[root] > 1:\n",
    "                return\n",
    "            l = leftChild[root]\n",
    "            if l != -1:\n",
    "                dfs(l)\n",
    "            r = rightChild[root]\n",
    "            if r != -1:\n",
    "                dfs(r)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        print(vis)\n",
    "        return all(x == 1 for x in vis)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        roots = []\n",
    "        s = set()\n",
    "        leng = 0\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if leftChild[i] >= 0:\n",
    "                s.add(leftChild[i])\n",
    "                edges[i].append(leftChild[i])\n",
    "                leng += 1\n",
    "            if rightChild[i] >= 0:\n",
    "                s.add(rightChild[i])\n",
    "                edges[i].append(rightChild[i])\n",
    "                leng += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in s:\n",
    "                roots.append(i)\n",
    "        \n",
    "        if len(roots) != 1:\n",
    "            return False\n",
    "        \n",
    "        if leng != n-1:\n",
    "            return False\n",
    "\n",
    "        root = roots[0]\n",
    "\n",
    "\n",
    "        nodes = 0\n",
    "        vis = [0]*n\n",
    "        def dfs(u):\n",
    "            nonlocal nodes\n",
    "            vis[u] = 1\n",
    "            nodes += 1\n",
    "            for v in edges[u]:\n",
    "                if not vis[v]:\n",
    "                    vis[v] = 1\n",
    "                    dfs(v)\n",
    "        dfs(root)\n",
    "        if nodes == n:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        # if False in self.visited:\n",
    "        #     return False\n",
    "        parent = [[] for _ in range(n)]\n",
    "        for i in range(len(leftChild)):\n",
    "            if leftChild[i] != -1:\n",
    "                parent[leftChild[i]].append(i)\n",
    "        for i in range(len(rightChild)):\n",
    "            if rightChild[i] != -1:\n",
    "                parent[rightChild[i]].append(i)\n",
    "        root = -1\n",
    "        for i in range(len(parent)):\n",
    "            if parent[i] == []:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return False\n",
    "        res = True\n",
    "        self.visited = [False]*n\n",
    "        res = res and self.dfs(root, leftChild, rightChild)\n",
    "        if False in self.visited:\n",
    "            return False\n",
    "        return res\n",
    "        \n",
    "    def dfs(self, curNum, leftChild, rightChild):\n",
    "        if curNum == -1:\n",
    "            return True\n",
    "        if self.visited[curNum]:\n",
    "            return False\n",
    "        self.visited[curNum] = True\n",
    "        res1 = self.dfs(leftChild[curNum], leftChild, rightChild)\n",
    "        res2 = self.dfs(rightChild[curNum], leftChild, rightChild)\n",
    "        return res1 and res2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        root_nodes = self.find_root(n, leftChild, rightChild)\n",
    "        if len(root_nodes) != 1:\n",
    "            return False\n",
    "\n",
    "        \n",
    "        num = self.get_deep(root_nodes[0],leftChild,rightChild)\n",
    "        print(num)\n",
    "        if num != n:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "        \n",
    "\n",
    "    def find_root(self,n,leftChild,rightChild):\n",
    "        no_root_nodes = leftChild\n",
    "        no_root_nodes.extend(rightChild)\n",
    "        all_nodes = list(range(-1,n))\n",
    "        data = {}\n",
    "        for i in no_root_nodes:\n",
    "            if i in data.keys() and i != -1:\n",
    "                return []\n",
    "            else:\n",
    "                data[i] = 1\n",
    "\n",
    "        root_nodes = list(set(all_nodes)^set(no_root_nodes))\n",
    "        return root_nodes   \n",
    "\n",
    "    def get_deep(self,start, leftChild, rightChild):\n",
    "        left = leftChild[start]\n",
    "        right = rightChild[start]\n",
    "        num = 0\n",
    "        if left == -1 and right == -1:\n",
    "            return 1\n",
    "        if left == right:\n",
    "            return -1000\n",
    "        if left != -1:\n",
    "            num += self.get_deep(left, leftChild, rightChild)\n",
    "        if right != -1:\n",
    "            num +=  self.get_deep(right, leftChild, rightChild)\n",
    "        \n",
    "        return num + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "\n",
    "        parent= [i for i in range(n)]\n",
    "        indgree = [0]*n\n",
    "        count = n\n",
    "        for i in range(n):\n",
    "            l = leftChild[i]\n",
    "            if l!=-1:\n",
    "                indgree[l] += 1\n",
    "            r = rightChild[i]\n",
    "            if r!=-1:\n",
    "                indgree[r] += 1\n",
    "        \n",
    "        root = []\n",
    "        for i in range(n):\n",
    "            if indgree[i] ==0:\n",
    "                root.append(i)\n",
    "        if len(root)!=1: \n",
    "            return False\n",
    "        rt = root[0]\n",
    "        visited = set()\n",
    "        ok =True\n",
    "        def dfs(root):\n",
    "            nonlocal ok\n",
    "            if root in visited:\n",
    "                ok = False\n",
    "                return\n",
    "            visited.add(root)\n",
    "            l = leftChild[root]\n",
    "            r = rightChild[root]\n",
    "            if l!=-1: \n",
    "                dfs(l)\n",
    "            if r!=-1: \n",
    "                dfs(r)\n",
    "        dfs(rt)\n",
    "        return ok and len(visited)==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        # isV=[0]*n\n",
    "        def dfs(i):\n",
    "            if i==-1:\n",
    "                return True\n",
    "            if isV[i]==1:\n",
    "                return False\n",
    "            nonlocal count\n",
    "            count+=1\n",
    "            isV[i]=1\n",
    "            left=leftChild[i];right=rightChild[i]\n",
    "            return dfs(left) and dfs(right)\n",
    "        for i in range(n):\n",
    "            isV=[0]*n\n",
    "            count=0\n",
    "            if dfs(i)==False:\n",
    "                return False\n",
    "            else:\n",
    "                if count==n:\n",
    "                    return True\n",
    "        return False\n",
    "            \n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        d1 = dict()\n",
    "        d2 = dict()\n",
    "        root = -1\n",
    "        for i in range(len(leftChild)):\n",
    "            if i not in leftChild and i not in rightChild:\n",
    "                if root == -1:\n",
    "                    root = i\n",
    "                else:\n",
    "                    return False\n",
    "            elif i in leftChild and i in rightChild:\n",
    "                return False\n",
    "        if root == -1:\n",
    "            return False\n",
    "        is_visited = set()\n",
    "        count = 0\n",
    "        def dfs(i):\n",
    "            if i in is_visited:\n",
    "                return False\n",
    "            else:\n",
    "                is_visited.add(i)\n",
    "            nonlocal count\n",
    "            count += 1\n",
    "            if leftChild[i] != -1:\n",
    "                dfs(leftChild[i])\n",
    "            if rightChild[i] != -1:\n",
    "                dfs(rightChild[i])\n",
    "        dfs(root)\n",
    "        if count == len(leftChild):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "\n",
    "        parent= [i for i in range(n)]\n",
    "        indgree = [0]*n\n",
    "        count = n\n",
    "        for i in range(n):\n",
    "            l = leftChild[i]\n",
    "            if l!=-1:\n",
    "                indgree[l] += 1\n",
    "            r = rightChild[i]\n",
    "            if r!=-1:\n",
    "                indgree[r] += 1\n",
    "        \n",
    "        root = []\n",
    "        for i in range(n):\n",
    "            if indgree[i] ==0:\n",
    "                root.append(i)\n",
    "        if len(root)!=1: \n",
    "            return False\n",
    "        rt = root[0]\n",
    "        visited = set()\n",
    "        ok =True\n",
    "        def dfs(root):\n",
    "            nonlocal ok\n",
    "            if root in visited:\n",
    "                ok = False\n",
    "                return\n",
    "            visited.add(root)\n",
    "            print(root)\n",
    "            l = leftChild[root]\n",
    "            r = rightChild[root]\n",
    "            if l!=-1: \n",
    "                print(root, 'left')\n",
    "                dfs(l)\n",
    "            if r!=-1: \n",
    "                print(root, 'right')\n",
    "                dfs(r)\n",
    "        dfs(rt)\n",
    "        return ok and len(visited)==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        vis = [0] * n\n",
    "        G = defaultdict(list)\n",
    "        I = [0] * n\n",
    "        for idx,i in enumerate(leftChild):\n",
    "            if i == -1:continue\n",
    "            G[idx].append(i)\n",
    "            I[i] += 1\n",
    "        for idx,i in enumerate(rightChild):\n",
    "            if i == -1:continue\n",
    "            G[idx].append(i)\n",
    "            I[i] += 1\n",
    "        for i in I:\n",
    "            if i > 1:return False\n",
    "        strt = -1\n",
    "        for idx,i in enumerate(I):\n",
    "            if not i:\n",
    "                strt = idx;break\n",
    "        def dfs(cur,par):\n",
    "            if par in G[cur]:return False\n",
    "            vis[cur] = 1\n",
    "            for nxt in G[cur]:\n",
    "                dfs(nxt,cur)\n",
    "            return\n",
    "        dfs(strt,-1)\n",
    "        return sum(vis) == n\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:\n",
    "        c = Counter(leftChild + rightChild)\n",
    "        root = set(range(n))\n",
    "        for i in range(n):\n",
    "            if i in c:\n",
    "                root.remove(i)\n",
    "                if c[i] > 1:\n",
    "                    return False\n",
    "        \n",
    "        if len(root) != 1:\n",
    "            return False\n",
    "        \n",
    "        vis = set()\n",
    "        def dfs(node):\n",
    "            vis.add(node)\n",
    "            if leftChild[node] != -1:\n",
    "                dfs(leftChild[node])\n",
    "            if rightChild[node] != -1:\n",
    "                dfs(rightChild[node])\n",
    "\n",
    "        dfs(list(root)[0])\n",
    "        return len(vis) == n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
